package com.haidechizi.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: wangdejun
 * @create: 2020-04-18 16:05
 **/
public class _436_寻找右区间 {

    public int[] findRightInterval(int[][] intervals) {
        if (intervals.length == 1) {
            return new int[]{-1};
        }
        Map<int[], Integer> map = new HashMap<>();
        for (int i = 0; i < intervals.length; i++) {
            map.put(intervals[i], i);
        }
        Integer min;
        sort(intervals);
        int[] result = new int[intervals.length];
        for (int i = 0; i < intervals.length - 1; i++) {
            min = null;
            int left = intervals[i][1];
            for (int j = i + 1; j < intervals.length; j++) {
                int right = intervals[j][0];
                if (right >= left) {
                    min = map.get(intervals[j]);
                    break;
                }
            }
            if (min == null) {
                min = -1;
            }
            result[map.get(intervals[i])] = min;
        }
        result[map.get(intervals[intervals.length - 1])] = -1;
        return result;

    }

    public void sort(int[][] intervals) {
        for (int i = 0; i < intervals.length; i++) {
            for (int j = 0; j < intervals.length - 1 - i; j++) {
                if (intervals[j][0] > intervals[j + 1][0]) {
                    int[] temp = intervals[j];
                    intervals[j] = intervals[j + 1];
                    intervals[j + 1] = temp;
                }
            }
        }
    }
}
